package com.zjj.lbw.interview.tree;

import com.zjj.lbw.interview.common.TreeNode;

import java.util.*;

/**
 * @author zhanglei.zjj
 * @description 二叉树前序遍历-递归
 * @date 2023/9/3 11:35
 */
public class BinaryTreePreOrder {
    /**
     * 前序遍历-递归
     * @param root
     */
    public static void preorderRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        preorderRecursion(root.left);
        preorderRecursion(root.right);
    }

    /**
     * 前序遍历-迭代
     * @param root
     */
    public static void preorderIteration(TreeNode root) {
        if (root != null) {
            Deque<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode headeNode = stack.pop();
                if (headeNode != null) {
                    System.out.println(headeNode.val);
                    stack.push(headeNode.right);
                    stack.push(headeNode.left);
                }
            }
        }
    }

    /**
     * 前序遍历-morris遍历
     * @param root
     */
    public static void preorderMorris(TreeNode root) {
        if (root != null) {
            // root表示当前节点，mostRight表示root的左孩子的最右节点
            TreeNode mostRight = null;
            while (root != null) {
                mostRight = root.left;
                // 如果 mostRight 为null，说明遍历到了叶子节点
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != root) {
                        mostRight = mostRight.right;
                    }
                    // 构造线索指针
                    // mostRight的右孩子指向空，让其指向root，root向左移动
                    if (mostRight.right == null) {
                        mostRight.right = root;

                        // 对前序遍历来说，当前节点已经构建完线索指针，就打印
                        System.out.println(root.val);

                        // 当前节点-线索指针构建完毕，开始处理下一个节点
                        root = root.left;
                        continue;
                    }
                    // 当前线索指针已经指向本节点，说明已经构建过线索指针，是在执行回溯的过程
                    if (mostRight == root) {
                        // 为了保证树结构不被破坏，需要删除线索指针
                        mostRight = null;
                    }
                } else {
                    // 如果左子节点为空，也直接打印
                    System.out.println(root.val);
                }
                // 要么是遍历到叶子节点回溯，要么是当前节点没有左节点，直接去处理右节点
                root = root.right;

            }
        }
    }

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        preorderRecursion(node1);
//        preorderIteration(node1);
        preorderMorris(node1);
    }
}
